#!/usr/bin/python

'''
'''
class SortedArray:
    def __init__(self):
        pass

    def forwardSort(self, dataToSort):
        raise NotImplementedError('forwardSort Method must be defined!')

    def reverseSort(self, dataToSort):
        raise NotImplementedError('reverseSort Method must be defined!')

class Heap(SortedArray):
    def __init__(self):
        self.data = []
        self.dataSize = 0

    def __repr__(self):
        return "%r" %self.data

    def getHeapSize(self):
        return self.heapSize

    def decrementHeapSize(self):
        self.heapSize = self.heapSize - 1

    def getDataSize(self):
        return self.dataSize

    def setData(self, dataArray):
        self.data = list(dataArray[:])
        self.heapSize = len(self.data)
        self.dataSize = len(self.data)

    def getData(self):
        '''
        '''
        return self.data

    def __leftPosition(self, position):
        '''
        '''
        return position*2 + 1

    def __rightPosition(self, position):
        '''
        max-heap Method
        '''
        return position*2 + 2

    def heapify(self, position):
        '''
        '''
        if position >= (self.getHeapSize() - 1)/2:
            return

        print self.data

        left = self.__leftPosition(position)
        right = self.__rightPosition(position)
        larger = position

        print "LOG: position=%d left=%d right=%d" %(position, left, right)

        # search for a larger value
        if self.data[position] < self.data[left]:
            larger = left
        if right < self.getHeapSize() and self.data[larger] < self.data[right]:
            larger = right

        print "LOG: larger=%d, getHeapSize=%d" %(larger, self.getHeapSize())

        if position != larger:
            t = self.data[position]
            self.data[position] = self.data[larger]
            self.data[larger] = t
            self.heapify(larger)
        return

    def buildMaxHeap(self):
        '''
        '''
        # for each element of self.data, which is a intermediate node of the
        # equivalent binary tree, heapify is called
        for i in range((self.getHeapSize() - 1)/2, -1, -1):
            # Calling heapify to conform that 'i' adhers to heap property
            print "Calling for i=%d and data=%s" %(i, self.data)
            self.heapify(i)

        # At this point, the array has a max heap property and its largest
        # element is at the root
        return

    def heapSort(self, arrayToSort):
        '''
        '''
        # Fixing the array to be sorted as an internal element of Heap Object
        self.setData(arrayToSort)

        print "LOG: heapSort: data=[%s], heapSize=[%d]" %(self.data, \
            self.getHeapSize())

        for i in range(0,len(self.data)):
            # First Call to building the max Heap
            self.buildMaxHeap()
      
            # swap the first and last element, for in-place sort
            largest = self.data[0]
            self.data[0] = self.data[self.getHeapSize() - 1]
            self.data[self.getHeapSize() - 1] = largest
            self.decrementHeapSize()

            print "LOG: Calling buildHeap: data=%s, heapSize=%d" %(self.data, \
                self.getHeapSize())
        return

    def forwardSort(self, arrayToSort):
        '''
        returns an array
        '''
        self.heapSort(arrayToSort)
        return self.data

    def reverseSort(self, arrayToSort):
        pass

newHeap = Heap()
print "%r" %newHeap.forwardSort((5,4,3,2,1,100,23,4,6,7,88,33,11,2,1,6,7,8,89))
